# 进制转化
# 将K进制的数字转化为 10 进制
# 输入： k:int,x:str

int_to_char="0123456789ABCDEF"
char_to_int={}
for idx,chr in enumerate(int_to_char):
    char_to_int[chr]=idx

# print(char_to_int)

# n: x[0]*k^(n-1)+x[1]*k^(n-2)
def k_to_10(k,x):
    ans=0
    x=x[::-1]# 将str进行翻转
    for i in range(len(x)):# 0:9 - >0:9  "A":"F" ->10:15
        ans=ans+char_to_int[x[i]]*k**i
    return ans


k=8
x="3506"
print(k_to_10(k,x))


# 10进制转任意进制
def ten_to_k(x,k):
    # 输入：十进制数字x,转换成k进制
    ans=""
    while x!=0:
        ans+=int_to_char[x%k]
        x//=k
    return ans[::-1]
x=19
k=2
print(ten_to_k(x,k))


# 任意的数据转换
t=int(input())
for _ in range(t):
    N,M=map(int,input().split())
    x=input()
    # 将N进制的x转成M进制
    # 1.将N进制的x转为十进制的y
    # 2.将十进制的y转成M进制的z
    y=k_to_10(N,x)
    z=ten_to_k(y,M)
    print(z)